package linkedList.辅助栈或者辅助map;

import linkedList.BaseLinkedListTest;
import po.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 链表中的下一个更大节点1019.java
 * @Description  https://leetcode-cn.com/problems/next-greater-node-in-linked-list/
 * 给定一个长度为 n 的链表 head
 *
 * 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值
 *
 */
public class 链表中的下一个更大节点1019 extends BaseLinkedListTest {

    /**
     * todo  参考739题 https://leetcode-cn.com/problems/daily-temperatures/solution/leetcode-tu-jie-739mei-ri-wen-du-by-misterbooo/
     */
    public int[] nextLargerNodes(ListNode head) {
        //todo 把链表转化为集合
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        //todo 栈中保存的是集合的下标
        Stack<Integer> stack = new Stack<>();
        int[] ints = new int[list.size()];
        for (int i = 0; i < ints.length; i++) {
            /**
             *todo
             * 1. 如果栈不为空，获取栈顶的索引值peekIndex
             * 2. 比较集合中索引为peekIndex的值跟当前循环到的值大小
             *    2.1 如果新加的比索引为peekIndex的值小，就把其索引放到栈顶
             *    2.2 如果新加的比索引为peekIndex的值大，则把栈顶的值弹出，循环1到2.2，直到栈顶的索引所在的值比当前值大，然后把栈顶的索引值所在的位置的值，放在返回的数组对应的索引的位置
             * 3. 把最新的值入栈
             */
            while (!stack.isEmpty() && list.get(stack.peek()) < list.get(i)) {
                Integer peekIndex = stack.pop();
                //todo 把栈顶的索引值所在的位置的值，放在返回的数组对应的索引的位置
                ints[peekIndex]=list.get(i);
            }
            //todo 把最新的值入栈
            stack.push(i);
        }
        return ints;
    }
}
